Not Applicable
Not Applicable
Not Applicable
1. Field of Invention
This invention relates to the field of data compression and decompression of the compressed data.
2. Description of the Related Art
Data compression is a process of converting data such that the converted data can be encoded in fewer bits or bytes. When being decompressed, the compressed data is recovered to its original form. Compressed data saves data storage since smaller-sized data takes less space to store. Compressed data can also enhance data transmission rates since smaller-sized data requires less time to transmit. Compression techniques have long been used in storage media such as tapes, disks, and flash cards, as well as communication equipment, such as the modem and Ethernet. With the rapidly growing demand for the Internet as well as handheld and wireless devices, compression plays an even bigger role than ever in terms of data transmission and storage.
As shown in FIG. 1, a typical LZ data compression method processes an input data stream 10 to generate a compressed output data stream 17 by comparing an unprocessed data portion 12 of the input data stream 10 to already processed data in a history buffer 11. If a data string 13 found in the history buffer 11 matches a current data string 14 in the unprocessed data portion 12, the current data string 14 is replaced by a pointer (P, L) that corresponds to an offset P 15 and a match length L 16. The offset P 15 and match length L 16 are then encoded individually with either a fixed-length coding or a variable-length coding process. Thus, the current data string 14 is represented by a shorter coded pointer data (P, L) 18 in the compressed output data stream 17.
As shown in FIG. 2, fixed-length coding uses a fixed number of bits to encode a range of numbers. For example, if the number xe2x80x9c7xe2x80x9d were coded in a 13-bit fixed-length coding scheme, the encoded bit string would be xe2x80x9c0000000000111xe2x80x9d. In another case, if the number xe2x80x9c4096xe2x80x9d were coded in a 13-bit fixed-length coding scheme, the encoded bit string would be xe2x80x9c1000000000000xe2x80x9d. Thus, an n-bit fixed-length coding scheme encodes up to 2n numbers ranging from 0 to (2nxe2x88x921). Variable-length coding, on the other hand, uses a variable number of bits to encode a range of numbers. There are many different variable-length coding schemes suited to different needs. FIG. 3 illustrates an example of a variable-length coding table that encodes up to 8,191 numbers ranging from 0 to 8,190. Variable-length coding typically encodes smaller numbers in fewer bits and larger numbers in more bits. For example, coding the number xe2x80x9c4096xe2x80x9d using the variable-length coding table shown in FIG. 3 would take 25 bits. However, coding the number xe2x80x9c7xe2x80x9d using the same variable-length coding table would only take 7 bits. Thus, compared to variable-length coding, fixed-length coding generally tends to be more efficient in coding larger numbers, but less efficient in coding smaller numbers.
How to encode data efficiently is essential to achieving a good compression result. Prior methods typically encode match length L 16 with variable-length coding and offset P 15 with fixed-length coding. While match length L 16 is normally a small number, offset P 15 falls within a wide range of values determined by the size of the history buffer 11. Offset P 15 has an upper bound that increases as the size of the history buffer 11 increases. Thus, coding offset P 15 strictly with fixed-length coding as do most of the prior methods is less desirable when offset P 15 turns out to be a small number, e.g. xe2x80x9c7xe2x80x9d. On the other hand, coding offset P 15 strictly in variable-length coding is less desirable either when offset P 15 happens to be a large number, e.g. xe2x80x9c4096xe2x80x9d. Thus, combining different coding schemes into a single coding scheme is able to maximize the efficiencies of data encoding.
Since smaller data requires fewer bits to encode prior methods try to reduce the number of bits to encode data through methods such as replacing a matching data string with a pointer data (P, L) as illustrated in FIG. 1. However, it is desirable to further reduce the value of a data before encoding.
A data encoding and decoding system for improving data compression performance is provided in accordance with the principles of this invention. The data encoding and decoding system comprises a composite fixed-variable-length coding process and an offset-difference coding process for encoding and decoding data. The encoding process of composite fixed-variable-length coding encodes an input data by first comparing the input data to a predetermined threshold, then selecting a coding scheme from two preselected coding schemes and encoding the input data in accordance with the selected coding scheme. The encoding process of composite fixed-variable-length coding also generates an identifier to indicate the selected coding scheme if the response to comparing the input data with a predetermined threshold differs from a statistically determined response. The decoding process of composite fixed-variable-length coding first detects if an identifier exists in a codeword in a coded data stream, then decodes the codeword with a coding scheme that was selected in the corresponding encoding process.
A composite coding system provided in accordance with the principles of this invention encodes a paired input data by encoding the statistically larger one of the paired input data with a composite fixed-variable-length coding process and the statistically smaller one of the paired input data with a stand-alone coding process.
The encoding process of offset-difference coding encodes a paired input data by first determining the greater of the two input data, then calculating the difference between the larger input data and the smaller input data, replacing the larger input data with the calculated difference, and encoding said calculated difference and the smaller input data. The encoding process of offset-difference coding also generates an indicator to indicate the input data that has been replaced if said input data is not statistically larger. The decoding process of offset-difference coding first detects if an indicator exists in a codeword in a coded data stream, then decodes and reconstructs the original data.
The composite fixed-variable-length coding process described in accordance with the principles of this invention combines different coding schemes into a single coding scheme to encode a data. It thus maximizes the efficiencies and minimizes the deficiencies of a coding scheme. The offset-difference coding process described in accordance with the principles of this invention minimizes the number of bits required to encode a data by further reducing the value of the data. Data with smaller values require fewer bits to encode, especially in a variable-length coding scheme. Thus, the two processes improve the compression performance of LZ-based compression methods without compromising the memory resource or compression/decompression speed. The two processes may be used independently or together depending on the application.